# 作者: YWH
# 2025年01月02日18时13分11秒
# 981474892@qq.com

#目标，实现建立二叉树、并对二叉树进行前中后序遍历


class Node:
    """
    创建结点，类似结构体。二叉树包含根结点、左孩子右孩子
    """
    def __init__(self, elem=-1, lchild=None, rchild=None):
        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild


class BinaryTree:
    def __init__(self):
        self.root = None
        self.help_queue = []  # 辅助队列

    def level_build_tree(self, node: Node):
        if self.root is None:  # 树根是空的，则根节点赋值，同时加入结点。
            self.root = node
            self.help_queue.append(node)
        else:
            self.help_queue.append(node)
            if self.help_queue[0].lchild is None:  # 如果当前结点左孩子空，则放入左孩子
                self.help_queue[0].lchild = node
            else:
                self.help_queue[0].rchild = node  # 结点右孩子空，放右孩子
                self.help_queue.pop(0)  # 有右孩子则这个“二叉树”满了，出队

    def pre_order(self, current_node: Node):
        if current_node:
            print(current_node.elem, end=' ')#打印当前结点，然后左子树遍历，右子树遍历。根左右
            self.pre_order(current_node.lchild)
            self.pre_order(current_node.rchild)

    def mid_order(self, current_node: Node):
        if current_node:
            self.mid_order(current_node.lchild)#左根右
            print(current_node.elem, end=' ')
            self.mid_order(current_node.rchild)

    def last_order(self, current_node: Node):
        if current_node:
            self.last_order(current_node.lchild)#左右根
            self.last_order(current_node.rchild)
            print(current_node.elem, end=' ')

    def level_order(self):#层次遍历思想，根结点->左孩子->右孩子
        help_queue = []
        help_queue.append(self.root)  # 树根入队
        while help_queue:#只要辅助队列有结点就一直循环
            out_node: Node = help_queue.pop(0)  # 出队
            print(out_node.elem,end=' ')  # 不换行输出
            if out_node.lchild:#有左孩子，入队
                help_queue.append(out_node.lchild)
            if out_node.rchild:#有右孩子，入队
                help_queue.append(out_node.rchild)


if __name__ == '__main__':
    tree = BinaryTree()
    for i in range(1, 11):
        new_node = Node(i)  # 实例化结点
        tree.level_build_tree(new_node)  # 把结点放入树中
    tree.pre_order(tree.root)  # 前序遍历（深度优先）
    print('\n')
    print("-"*50)
    print()
    tree.mid_order(tree.root)
    print('\n')
    print("-" * 50)
    print()
    tree.last_order(tree.root)
    print('\n')
    print("-" * 50)
    print()
    tree.level_order()